package week01

import "fmt"

// 42. 接雨水
// https://leetcode-cn.com/problems/trapping-rain-water/

func trap(height []int) int {
	var ans = 0
	var stack []Rect
	for _, h := range height {
		var w = 0
		for len(stack) > 1 && stack[len(stack)-1].Height <= h {
			var top = stack[len(stack)-1]
			w += top.Width
			var bottom = top.Height
			stack = stack[:len(stack)-1]
			ans += w * max(0, min(stack[len(stack)-1].Height, h) - bottom)
		}
		stack = append(stack, Rect{h, w+1})
		fmt.Println(fmt.Sprintf("stack: %+v", stack))
	}
	return ans
}

type Rect struct {
	Height int
	Width int
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}